package com.wyd.tree;


class RedTreeNode{
    int key;
    RedTreeNode right,left,parent;
    boolean isRed;// true 为红色  false 为黑色
}
public class RedTree {

    RedTreeNode root;


    private void leftRotate(RedTreeNode x) {
        // 左旋操作
        // y = x.left
        // 1. temp =  y.right
        //  y.right = x
        // x.left = temp

        RedTreeNode y = x.right;

        RedTreeNode temp = y.left;

        // 旋转第一步 y 的父级别 x, 变成 左子节点

        // 之前y的左子节点 成为到原父级，的右子节点
        x.right = temp;
        if (temp != null){
            temp.parent = x;
        }
        y.parent = x.parent;

        if (x.parent == null){
            // x 是root 节点
            // y 就成为新的 root 节点
            this.root = y;
        }else{
            if (x.parent.left == x){
                // x 的左
                x.parent.left = y;
            }else{
                x.parent.right = y;
            }
        }
        // 更新下父级指向
        y.left = x;
        x.parent = y;

    }

    private void rightRotate(RedTreeNode x) {
        // 右旋操作
        // n = x.left
        // 1. temp =  n.right
        //  n.right = x
        // x.left = temp

        RedTreeNode y = x.left;
        RedTreeNode temp = y.right;


        // 之前y的左子节点 成为到原父级，的左子节点
        x.left = temp;
        if (temp != null){
            temp.parent = x;
        }

        if (x.parent == null){
            // x 是root 节点
            // y 就成为新的 root 节点
            this.root = y;
        }else{
            if (x.parent.left == x){
                // x 的左
                x.parent.left = y;
            }else{
                x.parent.right = y;
            }
        }


        // 旋转第一步 y 的父级别 x, 变成 右子节点
        y.right = x;
        x.parent = y;
    }


    public void  insert(int key){
        RedTreeNode redTreeNode = new RedTreeNode();
        redTreeNode.key = key;
        redTreeNode.isRed  = true;

        RedTreeNode curNode = this.root;
        RedTreeNode pNode = null;
        while (curNode != null){
            // 等于直接覆盖
//            if (key == curNode.key){
//
//            }
            pNode = curNode;
            if (key > curNode.key){
                if ( curNode.right == null){
                    pNode.right = redTreeNode;

                    break;
                }
                curNode =  curNode.right;

            }

            if (key < curNode.key){

                if ( curNode.left == null){
                    pNode.left = redTreeNode;
                    break;
                }
                curNode =  curNode.left;


            }
        }
        redTreeNode.parent = pNode;
        if (pNode == null){
            this.root = redTreeNode;
            setBlack(this.root);
            return;
        }

        // 插入完成

        // 开始做 红黑树平衡修正操作
//        this.printTree(this.root, 0);

        insertFixUp(redTreeNode);
    }

    private boolean isRed(RedTreeNode node){
        if (node == null){
            return false;
        }
        return node.isRed;
    }

    private void setBlack(RedTreeNode node){
        if (node != null){
            node.isRed = false;
        }
    }

    private void setRed(RedTreeNode node){
        if (node != null){
            node.isRed = true;
        }
    }



    private  void insertFixUp(RedTreeNode node){


        // 如果父亲节点是红色 时 需要判断是否做平衡
        while (node.parent != null && node.parent.isRed) {
            // 判断 uncle 红色
            // 判断 uncle 黑色
            // 父节点为祖父节点 左节点时
            RedTreeNode uncle = null;
            RedTreeNode parent = node.parent;
            RedTreeNode gparent = parent.parent;
            if (gparent.left == parent){
                uncle = gparent.right;
            }else {
                uncle = gparent.left;
            }

            if (isRed(uncle)){
                // 红色做变色操作
                // 父 叔 变成黑色
                // 祖父修改为 红色
                setBlack(parent);
                setBlack(uncle);
                setRed(gparent);
                node = gparent;
                continue;
            }


            // 黑色做旋转操作
            // RR
            // RL

            // LL //LR
            if (gparent.left == parent){
                // 左边的情况
                //分为 LL 和 LR
                // LL 祖父右旋
                // LR 父亲节点 先做一次左旋 再右旋
                if(!node.equals(parent.left)){
                    // LR 需要先做一次 左旋
                    leftRotate(parent);

                    RedTreeNode tmp = parent;
                    parent = node;
                    node = tmp;
                }

                setBlack(parent);
                setRed(gparent);
                rightRotate(gparent);
            }else {
                // 左边的情况
                //分为 RR 和 RL
                // RR 祖父右旋
                // RL 父亲节点 先做一次左旋 再右旋
                if(!node.equals(parent.right)){
                    // RL 需要先做一次 右旋
                    rightRotate(parent);

                    RedTreeNode tmp = parent;
                    parent = node;
                    node = tmp;
                }

                setBlack(parent);
                setRed(gparent);
                leftRotate(gparent);
            }
        }

        setBlack(this.root);
    }


    public void printTree(RedTreeNode node, int level) {
        if (node == null) {
            return;
        }


        printTree(node.right, level + 1);
        if (level != 0) {
            for (int i = 0; i < level - 1; i++)
            {
                System.out.print("|\t");
            }
            System.out.println("|-------" + node.key +"("+node.isRed+")");
        } else {
            System.out.println(node.key+"("+node.isRed+")");

        }

        printTree(node.left, level + 1);
    }

    public static void main(String[] args) {
        RedTree tree = new RedTree();

        tree.insert(1);
        tree.insert(2);
        tree.insert(4);

        tree.insert(3);
        tree.insert(5);
        tree.insert(6);



        tree.printTree(tree.root,0);


    }




}
